package com.leetcode.partition2;

import java.util.Arrays;

/**
 * @author `RKC`
 * @date 2021/8/23 17:54
 */
public class LC122买卖股票的最佳时机2 {

    public static int maxProfit(int[] prices) {
        return greedy(prices);
    }

    public static void main(String[] args) {
        int[] prices = {7, 1, 5, 10, 3, 6, 4};
        System.out.println(dynamicProgramming(prices));
        System.out.println(greedy(prices));
    }

    private static int greedy(int[] prices) {
        int answer = 0;
        for (int i = 1; i < prices.length; i++) {
            answer += Math.max(prices[i] - prices[i - 1], 0);
        }
        return answer;
    }

    /**
     * i天不持有股票时：
     * i天卖出了股票dp[i-1][1]+prices[i]；i-1天就不持有股票dp[i-1][0]
     * i天持有股票：
     * i天买入了股票dp[i-1][0]-prices[i]（相比121题，需要对上一次的收益有记录）；i-1天就持有股票dp[i-1][1]
     */
    private static int dynamicProgramming(int[] prices) {
        int[][] dp = new int[prices.length][2];
        dp[0][0] = 0;
        dp[0][1] = -prices[0];
        for (int i = 1; i < prices.length; i++) {
            dp[i][0] = Math.max(dp[i - 1][1] + prices[i], dp[i - 1][0]);
            dp[i][1] = Math.max(dp[i - 1][0] - prices[i], dp[i - 1][1]);
        }
        Arrays.stream(dp).forEach(item -> System.out.println(Arrays.toString(item)));
        return dp[prices.length - 1][0];
    }
}
